import java.util.*;

public class Test
{
    public static void main(String[] args) {
        BinarySearchTree Tree=new  BinarySearchTree();
//        int[] array={8,66,99,5,2,3,96,54,17};
        int[] array={10,6,14,4,8,12,16};
        for(int i:array){
            Tree.insert(i);
        }
//        Solution3.Convert(Tree.root);
        Solution3.display(Solution3.Convert(Tree.root));
    }
}



//非递归实现二叉搜索树转单链表
class Solution3 {
    static BinarySearchTree.TreeNode head=null;//链表根节点
    static BinarySearchTree.TreeNode prev=null;//当前节点的前驱节点
    public static BinarySearchTree.TreeNode Convert(BinarySearchTree.TreeNode root) {
        Stack<BinarySearchTree.TreeNode> mystack=new Stack<>();
        BinarySearchTree.TreeNode cur=root;
        while(!mystack.isEmpty()||cur!=null){
            while(cur!=null){
                mystack.push(cur);
                cur=cur.left;
            }
            BinarySearchTree.TreeNode top=mystack.pop();
            if(head==null) head=top;
            if(prev!=null){
                top.left=prev;
                prev.right=top;
            }
            prev=top;
            cur=top.right;
        }
        return head;
    }
    public static void display(BinarySearchTree.TreeNode root) {
        while(root!=null){
            System.out.print(root.val+" ");
            root=root.right;
        }
    }
}

//递归实现二叉搜索树转双链表
class Solution2 {
    static BinarySearchTree.TreeNode root=null;//链表根节点
    static BinarySearchTree.TreeNode prev=null;//当前节点的前驱节点
    public static BinarySearchTree.TreeNode Convert(BinarySearchTree.TreeNode pRootOfTree) {
        if(pRootOfTree==null) return null;
        Convert(pRootOfTree.left);
        //当左树递归完成时，此时的节点为链表的根节点
        if(root==null) root=pRootOfTree;
        if(prev!=null){
            pRootOfTree.left=prev;//当前节点的左边是前驱节点。
            prev.right=pRootOfTree;//前驱的后继是当前节点。
        }
        prev=pRootOfTree;
        Convert(pRootOfTree.right);
        return root;
    }
    public static void display(BinarySearchTree.TreeNode root) {
        while(root!=null){
            System.out.print(root.val+" ");
            root=root.right;
        }
    }
}
class Solution {
    public static int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            if (!set.contains(i)) {
                set.add(i);
            } else {
                set.remove(i);
            }
        }
        for (int i : nums) {
            if (set.contains(i)) return i;
        }
        return -1;
    }
}